package com.congee02;

public class MaxSubArray_DP {

    public int maxSubArray(int... nums) {

        int n = nums.length;
        int[][] dp = new int[n][n];

        int ans = Integer.MIN_VALUE;
        for (int i = 0 ; i < n ; i ++ ) {
            dp[i][i] = nums[i];
            ans = Math.max(ans, dp[i][i]);
        }

        for (int col = 1 ; col < n ; col ++ ) {
            for (int rowIndex = 0, colIndex = col ; colIndex < n ; rowIndex ++, colIndex ++ ) {
                dp[rowIndex][colIndex] = Math.max(
                        rowIndex + 1 < n ? dp[rowIndex + 1][colIndex] + nums[rowIndex] : Integer.MIN_VALUE,
                        dp[rowIndex][colIndex - 1] + nums[colIndex]
                );
                ans = Math.max(ans, dp[rowIndex][colIndex]);
            }
        }

        return ans;
    }

    public static void main(String[] args) {

        MaxSubArray_DP s = new MaxSubArray_DP();

        System.out.println(s.maxSubArray(1, 2, 3, 4));

    }

}
